package org.example.myleet.rosalind.kmp;

import org.example.myleet.rosalind.utils.FastaReader;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        solution.printFailureArray(FastaReader.parseFastaFromFile(path).get(0).getSequence());
    }

    private void printFailureArray(String sequence) {
        char c0 = sequence.charAt(0);
        int n = sequence.length();
        int[] P = new int[n];
        for (int j = 1; j < n; ++j) {
            int prevLongestSubLen = P[j - 1];
            char prefixTail = sequence.charAt(prevLongestSubLen);
            char curChar = sequence.charAt(j);
            if (prefixTail == curChar) {
                //如果最新的字符能和上一个最长子序列的长度的前缀结尾的下一个字符匹配的话，直接继续延长匹配长度即可
                P[j] = P[j - 1] + 1;
            } else {
                //但是遇到没有匹配上的情况，则最长子序列长度肯定小于等于上一个匹配的长度，需要从上一个最长匹配长度开始找更短的匹配
                int k = prevLongestSubLen - 1;
                for (; k >= 0; --k) {
                    //逐步缩减最大匹配长度
                    char suffixHead = sequence.charAt(j - k);
                    if (c0 == suffixHead) {
                        boolean found = true;
                        for (int s = j - k + 1, t = 1; s <= j;) {
                            char c1 = sequence.charAt(t);
                            char c2 = sequence.charAt(s);
                            if (c1 != c2) {
                                found = false;
                                break;
                            }
                            ++s;
                            ++t;
                        }
                        if (found) {
                            break;
                        }
                    }
                }
                if (k < 0) {
                    //代表找不到匹配的长度，给0
                    k = 0;
                } else {
                    ++k;
                }
                P[j] = k;
            }
        }
        StringBuilder res = new StringBuilder();
        for (int num : P) {
            res.append(num).append(' ');
        }
        res.deleteCharAt(res.length() - 1);
        System.out.println(res);
    }
}
